package codingforgreat.lchot150;

import java.util.HashMap;

public class Lc138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node p = head;
        while(p != null){
            map.put(p,new Node(p.val));
            p = p.next;
        }
        p = head;
        while(p != null){
            Node cl = map.get(p);
            cl.next = map.get(p.next);
            cl.random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
    public Node copyRandomList1(Node head) {
        if(head == null){
            return null;
        }
        Node cur = head;
        Node next = null;
        while(cur != null){
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        while(cur != null){
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        Node clone = head.next;;
        Node cH = head.next;
        while(cur != null){
            next = cur.next.next;
            if(next != null){
                clone.next = next.next;
            }
            cur.next = next;
            cur = next;
            if(cur != null){
                clone = cur.next;
            }else{
                clone.next = null;
            }
        }
        return  cH;
    }
}
